package main

import "fmt"

/*
全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 */

func permute(nums []int) [][]int {
	res := make([][]int, 0)
	// 记录已经遍历过的数
	visited := make(map[int]bool, len(res))


	var dfs func(path []int)
	dfs = func(path []int) {
		// 递归退出条件
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}
		for _, v := range nums {
			if visited[v] {
				continue
			}
			path = append(path, v)
			visited[v] = true
			dfs(path)
			path = path[:len(path)-1]
			visited[v] = false
		}
	}
	dfs([]int{})

	return res
}

func main() {
	fmt.Println(permute([]int{1,2,3}))
	
}
